package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC10 {
    public boolean isMatch(String s, String p) {
        if (null == s || null == p) {
            return false;
        }

        if (p.equals(".*")) {
            return true;
        }

        if (p.length() == 1) {
            return s.equals(p) || (s.length() == 1 && p.equals("."));
        }

        for (int i = p.length() - 1; i >= 0; --i) {
            // last bit is *
            if (p.charAt(i) == '*') {
                if (p.charAt(i - 1) == '.') {
                    // last second bit is .
                    for (int j = s.length(); j >= 0; --j) {
                        if (isMatch(s.substring(0, j), p.substring(0, i - 1))) {
                            return true;
                        }
                    }
                    return false;
                } else if (p.charAt(i - 1) != '*') {
                    // last second bit is numeric
                    int j = s.length() - 1;
                    for (; j >= 0 && s.charAt(j) == p.charAt(i - 1); --j) {
                        if (isMatch(s.substring(0, j + 1), p.substring(0, i - 1))) {
                            return true;
                        }
                    }
                    return isMatch(s.substring(0, j + 1), p.substring(0, i - 1));
                }
            }

            // last bit is .
            else if (p.charAt(i) == '.') {
                if (s.length() == 0) {
                    return false;
                }
                return isMatch(s.substring(0, s.length() - 1), p.substring(0, i));
            }

            // last bit is numeric
            else {
                if (s.length() == 0) {
                    return false;
                }
                return s.charAt(s.length() - 1) == p.charAt(i) && isMatch(s.substring(0, s.length() - 1), p.substring(0, i));
            }
        }

        return s.equals(p);
    }

    public static void main(String[] args) {
        LC10 an = new LC10();
        /**
         "aaabaaaababcbccbaab"
         "c*c*.*c*a*..*c*"
         */
        System.out.println(an.isMatch("aaabaaaababcbccbaab", "c*c*.*c*a*..*c*"));
    }
}
